Search for: All records

Abstract For a subset$$A$$of an abelian group$$G$$, given its size$$|A|$$, its doubling$$\kappa =|A+A|/|A|$$, and a parameter$$s$$which is small compared to$$|A|$$, we study the size of the largest sumset$$A+A'$$that can be guaranteed for a subset$$A'$$of$$A$$of size at most$$s$$. We show that a subset$$A'\subseteq A$$of size at most$$s$$can be found so that$$|A+A'| = \Omega (\!\min\! (\kappa ^{1/3},s)|A|)$$. Thus, a sumset significantly larger than the Cauchy–Davenport bound can be guaranteed by a bounded size subset assuming that the doubling$$\kappa$$is large. Building up on the same ideas, we resolve a conjecture of Bollobás, Leader and Tiba that for subsets$$A,B$$of$$\mathbb{F}_p$$of size at most$$\alpha p$$for an appropriate constant$$\alpha \gt 0$$, one only needs three elements$$b_1,b_2,b_3\in B$$to guarantee$$|A+\{b_1,b_2,b_3\}|\ge |A|+|B|-1$$. Allowing the use of larger subsets$$A'$$, we show that for sets$$A$$of bounded doubling, one only needs a subset$$A'$$with$$o(|A|)$$elements to guarantee that$$A+A'=A+A$$. We also address another conjecture and a question raised by Bollobás, Leader and Tiba on high-dimensional analogues and sets whose sumset cannot be saturated by a bounded size subset. 

Abstract Let be a ‐regular graph on vertices. Frieze, Gould, Karoński, and Pfender began the study of the following random spanning subgraph model . Assign independently to each vertex of a uniform random number , and an edge of is an edge of if and only if . Addressing a problem of Alon and Wei, we prove that if , then with high probability, for each nonnegative integer , there are vertices of degree in . 

Abstract The list Ramsey number , recently introduced by Alon, Bucić, Kalvari, Kuperwasser, and Szabó, is a list‐coloring variant of the classical Ramsey number. They showed that if is a fixed ‐uniform hypergraph that is not ‐partite and the number of colors goes to infinity, . We prove that if and only if is not ‐partite.